By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
What Article options are available ?   View Cart   

Separating ${AC}^0$ from Depth-2 Majority Circuits

Alexander A. Sherstov

pp. 2113-2129

BibTeX  Abstract Full Text:  PDF

Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates

Amir Shpilka

pp. 2130-2161

BibTeX  Abstract Full Text:  PDF

Breaking a Time-and-Space Barrier in Constructing Full-Text Indices

Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung

pp. 2162-2178

BibTeX  Abstract Full Text:  PDF

Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops

Mee Yee Chan, Wun-Tat Chan, Francis Y. L. Chin, Stanley P. Y. Fung, and Ming-Yang Kao

pp. 2179-2197

BibTeX  Abstract Full Text:  PDF

Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations

Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang

pp. 2198-2219

BibTeX  Abstract Full Text:  PDF

Polylogarithmic Independence Can Fool DNF Formulas

Louay M. J. Bazzi

pp. 2220-2272

BibTeX  Abstract Full Text:  PDF

On the Value of Coordination in Network Design

Susanne Albers

pp. 2273-2302

BibTeX  Abstract Full Text:  PDF

Metric Embeddings with Relaxed Guarantees

T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, and Aleksandrs Slivkins

pp. 2303-2329

BibTeX  Abstract Full Text:  PDF

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou

pp. 2330-2355

BibTeX  Abstract Full Text:  PDF

The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly

Leonard Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, and Petr Sosik

pp. 2356-2381

BibTeX  Abstract Full Text:  PDF

Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions

David J. Aldous, Charles Bordenave, and Marc Lelarge

pp. 2382-2410

BibTeX  Abstract Full Text:  PDF